package tree

import (
	"fmt"
	"strconv"
	"time"
)

type BanTreeNode struct {
	Data interface{}
	Deep int8
	LeftNode *BanTreeNode
	RightNode *BanTreeNode
}

/**
				2
		4				5
	1		8		6		7
		10
 */
func CreateExampleTree() *BanTreeNode{
	//根节点
	rootNode:=new(BanTreeNode)
	rootNode.Data = 2
	rootNode.Deep = 1

	btnode1:=new(BanTreeNode)
	btnode1.Data = 4
	btnode1.Deep = 2

	btnode2:=new(BanTreeNode)
	btnode2.Data = 5
	btnode2.Deep = 2

	btnode3:=new(BanTreeNode)
	btnode3.Data = 1
	btnode3.Deep = 3
	btnode4:=new(BanTreeNode)
	btnode4.Data = 8
	btnode4.Deep = 3
	btnode5:=new(BanTreeNode)
	btnode5.Data = 6
	btnode5.Deep = 3
	btnode6:=new(BanTreeNode)
	btnode6.Data = 7
	btnode6.Deep = 3

	btnode7:=new(BanTreeNode)
	btnode7.Data = 10
	btnode7.Deep = 4

	//4-5
	rootNode.LeftNode=btnode1
	rootNode.RightNode=btnode2
	
	//1-8
	rootNode.LeftNode.LeftNode = btnode3
	rootNode.LeftNode.RightNode = btnode4
	//6-7
	rootNode.RightNode.LeftNode = btnode5
	rootNode.RightNode.RightNode = btnode6

	//10
	rootNode.LeftNode.LeftNode.LeftNode = btnode7

	return rootNode

}

//中序遍历 左-根-右 1 4 8 2 6 5 7
func MidDisPlay(rootNode *BanTreeNode) {
	if rootNode != nil {
		MidDisPlay(rootNode.LeftNode)

		fmt.Println(rootNode.Data)

		MidDisPlay(rootNode.RightNode)
	}
}

//前序遍历 根-左-右 2 4 1 8 5 6 7
func PreDisPlay(rootNode *BanTreeNode) {
	if rootNode != nil {
		fmt.Println(rootNode.Data)

		PreDisPlay(rootNode.LeftNode)

		PreDisPlay(rootNode.RightNode)
	}
}


//2 4 5 1 8 6 7 层序遍历 广度优先遍历
func WidthDisPlay(rootNode *BanTreeNode) {

	//队列
	var que []*BanTreeNode
	que = append(que,rootNode)
	for len(que)>0 {

		if que[0].LeftNode!=nil{
			que = append(que,que[0].LeftNode)
		}
		if que[0].RightNode!=nil{
			que = append(que,que[0].RightNode)
		}

		fmt.Println(que[0].Data)

		//弹出第一个d
		que = que[1:]

		time.Sleep(time.Second)
	}

}

//打印树图
func PrePrint(rootNode *BanTreeNode) {

	//队列
	var que []*BanTreeNode
	que = append(que,rootNode) //
	deep := GetDeepByWith(rootNode)
	for len(que)>0 {

		restr := ""
		tmp := []int{}
		length := len(que) //第一层，第二层 。。。
		for length>0 {
			length--
			if que[0].LeftNode!=nil{
				que = append(que,que[0].LeftNode)
			}
			if que[0].RightNode!=nil{
				que = append(que,que[0].RightNode)
			}
			//把左右子树压入队列

			tmp = append(tmp,que[0].Data.(int))
			//弹出第一个
			que = que[1:]
		}

		for _, v := range tmp {
			str := getBlank(deep)
			restr += str + strconv.Itoa(v)
		}

		deep--

		fmt.Println(restr)
	}
}

func getBlank(deep int)string {
	var i int
	str := ""
	for i = 0; i < deep; i++ {
		str += "      "
	}
	return str
}

func GetDeep(rootNode *BanTreeNode) int {
	if rootNode == nil {
		return 0
	}

	left := GetDeep(rootNode.LeftNode)
	right := GetDeep(rootNode.RightNode)
	if left >= right {
		return left+1
	}

	return right+1
}

func GetDeepByWith(rootNode *BanTreeNode) int{
	deep := 0
	//队列
	var que []*BanTreeNode
	que = append(que,rootNode) //
	for len(que)>0 {

		length := len(que) //第一层，第二层 。。。
		for length>0 {
			length--
			if que[0].LeftNode!=nil{
				que = append(que,que[0].LeftNode)
			}
			if que[0].RightNode!=nil{
				que = append(que,que[0].RightNode)
			}
			//把左右子树压入队列

			//弹出第一个
			que = que[1:]
		}

		deep++

	}
	return deep

}
